package hard;

/**
 * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
 * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
 * 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
 * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 *
 * 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素
 * 链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FindMinimumInRotatedSortedArrayII {
    /**
     * 排序的数组一定要考虑使用二分查找。二分查找不一定要去查元素，也可以用来查找边界。
     * 该题的难点在于 元素存在相等的情况。我们知道 二分查找一般分为两个条件，即目标值小于mid 和 大于mid
     * 我们观察题目中提到的数组，当旋转次数 ＞ 1 且 除以数组长度的余数 !=0 时，有如下特征：
     * 即右边一部分比左边部分小，右边部分的最小值和左边部分的最大值构成分界。
     *
     * */
    class Solution {
        public int findMin(int[] nums) {
            int left = 0, right=nums.length-1;
            while(left < right){
                int mid = (left + right) / 2;
                // 如果右边比中间数小，则分界线在右边
                if(nums[right] < nums[mid]){
                    left = mid + 1; // 难点 细节！！！
                }
                else if(nums[right] > nums[mid]){
                    right = mid; // 难点 细节！！！
                }
                else if(nums[right] == nums[mid]){
                    right--;
                }
            }
            return nums[left];
        }
    }
}
